class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False
        M = len(matrix)
        N = len(matrix[0])
        if M == 0 or N == 0:
            return False
        if M <= 2 and N <= 2:
            for i in range(M):
                for j in range(N):
                    if matrix[i][j] == target:
                        return True
            return False
        else:
            mid_M = M // 2
            mid_N = N // 2
            if target == matrix[mid_M][mid_N]:
                return True
            else:
                if target > matrix[mid_M][mid_N]:
                    flag = self.searchMatrix(matrix[mid_M + 1:], target) or self.searchMatrix(
                        [matrix[i][mid_N + 1:] for i in range(mid_M + 1)], target)
                else:
                    flag = self.searchMatrix(matrix[: mid_M], target) or self.searchMatrix(
                        [matrix[i][:mid_N] for i in range(mid_M, M)], target)
                return flag


data = Solution()
# matrix = [[-1,3]]
# target = 3
# print(data.searchMatrix(matrix, target))
# matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
# target = 5
# print(data.searchMatrix(matrix, target))
# matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
# target = 20
# print(data.searchMatrix(matrix, target))
matrix = [[1], [2], [3], [4], [5]]
target = 0
print(data.searchMatrix(matrix, target))
